// ------------------------------------------------------------------------------------------------
// ---- Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein) ------------------------------------
// ---- Algoritmos de Seleção linear no Caso Médio e no Pior Caso (Capítulo 9) --------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <string>
#include <windows.h>
using namespace std;


int Selecao(int* A, int p, int r, int k);
int Selecao_aleat(int* vetor, int p, int r, int k);


void InsertionSort(int* vetor, int p, int r);
void HeapSort(int* vetor, int p, int r);


void imprimir_vetor(int* vetor, int N, string filename);


int main() {
    int i,j;

    // Cria um vetor
    int N = 10000000;
    int* vetor = new int[N];
    srand (time(NULL));
    for (i=0;i<N;i++) vetor[i] = rand()%10000;

    //imprimir_vetor(vetor,N,"entrada.txt");
    int k =  N/2;
    int t1 = GetTickCount();

    int valor0 = Selecao(vetor,0,N-1,k);
    int t2 = GetTickCount();

    int valor1 = Selecao_aleat(vetor,0,N-1,k);
    int t3 = GetTickCount();


    HeapSort(vetor, 0, N-1);
    int valor2 = vetor[k-1];
    imprimir_vetor(vetor,N,"saida.txt");

    cout<<"Valor0 = "<<valor0<<"/ Valor1 = "<<valor1<<"/ Valor2 = "<<valor2<<endl<<"Tempo0= "<<t2-t1<<" miliseg/ Tempo1 = "<<t3-t2<<" miliseg"<<endl;
    delete[] vetor;
    return 0;
}



// ------------------------------------------------------------------------------------------------
// ---- Algoritmo PARTICIONE ----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void trocar(int& x, int& y) {int z = x; x = y; y = z;}

int Particione_original(int* vetor, int p, int r) {
    int pivo = vetor[r];
    int j, i=p-1;
    for (j=p; j<r; j++) {
        if (vetor[j] <= pivo) {
            i++;
            trocar(vetor[i], vetor[j]);
        }
    }
    trocar(vetor[i+1], vetor[r]);
    return i+1;
}

int Particione_aleat(int* vetor, int p, int r) {
    srand (time(NULL));
    int pos_pivo = p + rand()%(r-p+1);
    trocar(vetor[pos_pivo], vetor[r]);
    return Particione_original(vetor,p,r);
}

int Particione(int* vetor, int p, int r, int pivo) {
    int j, i=p-1;
    for (j=p; j<r; j++) {
        if (vetor[j] < pivo) {
            i++;
            trocar(vetor[i], vetor[j]);
        } else if (vetor[j]==pivo) {
            trocar(vetor[j], vetor[r]);
            break;
        }
    }
    for (j=j; j<r; j++) {
        if (vetor[j] <= pivo) {
            i++;
            trocar(vetor[i], vetor[j]);
        }
    }
    trocar(vetor[i+1], vetor[r]);
    return i+1;
}

// ------------------------------------------------------------------------------------------------
// ---- Algoritmo SELECAO -------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
int Selecao_aleat(int* A, int p, int r, int k) {
    if (p==r) return A[p];
    int q = Particione_aleat(A,p,r);
    int i = q-p+1;
    if (k==i) return A[q];
    if (k<i) return Selecao_aleat(A,p,q-1,k);
    return Selecao_aleat(A,q+1,r,k-i);
}



int Selecao(int* A, int p, int r, int k) {
    int i, N=r-p+1;
    if (N<10) {
        if (k>N) k=N;
        InsertionSort(A,p,r);
        return A[p+k-1];
    }

    int tam_M = N/5;
    int* M = (int*) calloc(tam_M,sizeof(int));
    for (i=0; i<tam_M; i++) {
        InsertionSort(A, p+5*i, p+5*i+4);
        M[i] = A[p+5*i+2];
    }

    int pivo = Selecao(M, 0, tam_M-1, tam_M/2);
    free(M);

    int q = Particione(A, p, r, pivo);
    i = q-p+1;
    if (k==i) return A[q];
    if (k<i) return Selecao(A,p,q-1,k);
    return Selecao(A,q+1,r,k-i);
}


// ------------------------------------------------------------------------------------------------
// ---- Algoritmo INSERTIONSORT -------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void InsertionSort(int* vetor, int p, int r) {
    int i,j,carta;
    for (j=p+1;j<=r;j++) {
        carta = vetor[j];
        i = j-1;
        while ((i>=p)&&(vetor[i]>carta)) {
            vetor[i+1] = vetor[i];
            i--;
        }
        vetor[i+1] = carta;
    }
}


// ------------------------------------------------------------------------------------------------
// ---- Algoritmo HEAPSORT ------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void maxheapify(int* vetor, int i, int p, int r) {
    int m = i;
    int esq = p+2*(i-p)+1;
    int dir = p+2*(i-p)+2;
    if ((esq<r)&&(vetor[esq]>vetor[i])) m = esq;
    if ((dir<r)&&(vetor[dir]>vetor[m])) m = dir;
    if (m != i) {
        trocar(vetor[i], vetor[m]);
        maxheapify(vetor,m,p,r);
    }
}

void HeapSort(int* vetor, int p, int r) {
    int i;
    for (i=(r+p-1)/2; i>=p; i--) {
        maxheapify(vetor,i,p,r);
    }
    for (i=r;i>p;i--) {
        trocar(vetor[p], vetor[i]);
        r = r-1;
        maxheapify(vetor,p,p,r);
    }
}


// ------------------------------------------------------------------------------------------------
// ---- Imprimir vetor em arquivo -----------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void imprimir_vetor(int* vetor, int N, string filename) {
    if (filename=="") filename="saida.txt";
    ofstream arq;
    arq.open(filename.c_str());
    for (int i=0;i<N;i++) arq<<vetor[i]<<" ";
    arq.close();
}